package com.leetcode.www;

import java.util.HashMap;
import java.util.Map;
import java.util.Random;

/**
 * Creared with IntelliJ IDEA.
 * Description:给你一个整数数组 nums ，该数组具有以下属性：
 *
 * nums.length == 2 * n.
 * nums 包含 n + 1 个 不同的 元素
 * nums 中恰有一个元素重复 n 次
 * 找出并返回重复了 n 次的那个元素。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/n-repeated-element-in-size-2n-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * User:yxd
 * Date:2022-05-22
 * Time:15:38
 */
public class Everyday961 {
    public int repeatedNTimes(int[] nums) {
        //我们可以每次随机选择两个不同的下标，判断它们对应的元素是否相等即可。如果相等，那么返回任意一个作为答案。
        int n = nums.length;
        Random random = new Random();

        while (true) {
            int x = random.nextInt(n), y = random.nextInt(n);
            if (x != y && nums[x] == nums[y]) {
                return nums[x];
            }
        }
    }

    public int repeatedNTimes1(int[] nums) {
        int n = nums.length;
        for (int gap = 1; gap <= 3; ++gap) {
            for (int i = 0; i + gap < n; ++i) {
                if (nums[i] == nums[i + gap]) {
                    return nums[i];
                }
            }
        }
        // 不可能的情况
        return -1;
    }

    public int repeatedNTimes2(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();
        int count = nums.length / 2;
        int x = 0;
        for(int i = 0;i < nums.length;i++){
            if(!map.containsKey(nums[i])){
                map.put(nums[i],1);
            }else{
                map.put(nums[i],map.get(nums[i]) + 1);
            }
            if(map.get(nums[i]) == count){
                x = nums[i];
                break;
            }
        }
        return x;

    }
}
